// https://www.lintcode.com/problem/unique-paths-ii/

public class Solution {
    /**
     * @param obstacleGrid: A list of lists of integers
     * @return: An integer
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // write your code here
        int rows = obstacleGrid.length, cols = obstacleGrid[0].length;
        int[][] cache = new int[rows][];
        for (int row = 0; row < rows; ++row) {
            cache[row] = new int[cols];
            for (int col = 0; col < cols; ++col) {
                cache[row][col] = -1;
            }
        }
        cache[0][0] = 1 - obstacleGrid[0][0];
        return _uniquePathsWithObstacles(rows - 1, cols - 1, obstacleGrid, cache);
    }
    
    private int _uniquePathsWithObstacles(int row, int col, int[][] obstacleGrid,int[][] cache) {
        if (cache[row][col] >= 0) {
            return cache[row][col];
        }
        int ret = 0;
        if (0 == obstacleGrid[row][col]) {
            if ((row > 0) && (0 == obstacleGrid[row - 1][col])) {
                ret += _uniquePathsWithObstacles(row - 1, col, obstacleGrid, cache);
            }
            if ((col > 0) && (0 == obstacleGrid[row][col - 1])) {
                ret += _uniquePathsWithObstacles(row, col - 1, obstacleGrid, cache);
            }
        }
        cache[row][col] = ret;
        return ret;
    }
}